import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

public class QuickUnionUF {
  private int[] id; // 分量ID
  private int count; // 分量数量

  public QuickUnionUF(int N) {
    count = N;// 初始化分量数量和id数组
    id = new int[N];
    for (int i = 0; i < N; i++) {
      id[i] = i; // 设置每个数组的值为自己的索引
    }
  }

  public int count() {
    return count; // 返回分量数量
  }

  // quick-union 算法

  // 获取到根节点
  private int find(int p) {
    while (p != id[p]) {
      p = id[p];
    }
    return p;
  }

  public void union(int p, int q) {
    int pRoot = find(p);
    int qRoot = find(q);

    if (pRoot == qRoot) {
      return; // 如果根节点相同则不做操作;
    }

    id[pRoot] = qRoot;// 链接两个根节点
    count--;
  }

  public static void main(String[] args) {
    int N = StdIn.readInt();
    StdOut.println("N === " + N);
    QuickFindUF uf = new QuickFindUF(N);
    while (!StdIn.isEmpty()) {
      int p = StdIn.readInt();
      int q = StdIn.readInt();
      if (uf.connected(p, q)) {
        continue;
      }
      uf.union(p, q);
      StdOut.println(p + " " + q);
    }
    StdOut.println(uf.count() + "components");
  }
}
